package com.test.daily.leetcode.y2022.m06.day0605.v01;

import java.util.*;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/6/5 上午 09:09
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        public int value;
        public int in;
        public int out;
        public ArrayList<Node> nodes;
        public ArrayList<Edge> edges;

        public Node(int value) {
            this.value = value;
            nodes = new ArrayList<>();
            edges = new ArrayList<>();
        }
    }

    public static class Edge {
        public Node from;
        public Node to;
        public int weight;

        public Edge(Node from, Node to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public class Graph {
        public ArrayList<Node> nodes;
        public ArrayList<Edge> edges;
    }

    public static class UnionFind {
        public HashMap<Node, Node> fatherMap;
        public HashMap<Node, Integer> sizeMap;

        public UnionFind() {
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
        }

        public void makeSets(Graph graph) {
            fatherMap.clear();
            sizeMap.clear();
            for (Node node : graph.nodes) {
                sizeMap.put(node, 1);
                fatherMap.put(node, node);
            }
        }

        public Node findFather(Node node) {
            Stack<Node> stack = new Stack<>();
            Node father = fatherMap.get(node);
            while (node != fatherMap.get(node)) {
                stack.push(node);
                node = fatherMap.get(father);
            }
            while (!stack.isEmpty()) {
                fatherMap.put(stack.pop(), node);
            }
            return node;
        }

        public boolean isSameSet(Node a, Node b) {
            return findFather(a) == findFather(b);
        }

        public void union(Node a, Node b) {
            Node aDai = findFather(a);
            Node bDai = findFather(b);
            if (aDai != bDai) {
                int aSize = sizeMap.get(aDai);
                int bSize = sizeMap.get(bDai);
                if (aSize > bSize) {
                    sizeMap.put(a, aSize + bSize);
                    sizeMap.remove(b);
                    fatherMap.put(bDai, aDai);
                } else {
                    sizeMap.put(b, aSize + bSize);
                    sizeMap.remove(a);
                    fatherMap.put(aDai, bDai);
                }
            }
        }
    }

    public static class MyEdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

    public static Set<Edge> kruskalMST(Graph graph) {
        UnionFind unionFind = new UnionFind();
        unionFind.makeSets(graph);
        PriorityQueue<Edge> pq = new PriorityQueue<>(new MyEdgeComparator());
        for (Edge edge : graph.edges) {
            pq.add(edge);
        }
        HashSet<Edge> sets = new HashSet<>();
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (!unionFind.isSameSet(edge.from, edge.to)) {
                unionFind.union(edge.from, edge.to);
                sets.add(edge);
            }
        }
        return sets;
    }

    public static Set<Edge> primMST(Graph graph) {
        Set<Edge> result = new HashSet<>();
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        Set<Node> nodeSet = new HashSet<>();
        for (Node node : graph.nodes) {
            if (!nodeSet.contains(node)) {
                nodeSet.add(node);
                for (Edge edge : node.edges) {
                    pq.add(edge);
                }
                while (!pq.isEmpty()) {
                    Edge newEdge = pq.poll();
                    Node toNode = newEdge.to;
                    if (!nodeSet.contains(toNode)) {
                        result.add(newEdge);
                        nodeSet.add(toNode);
                        for (Edge newNextEdge : toNode.edges) {
                            pq.add(newNextEdge);
                        }
                    }
                }

            }
        }
        return result;
    }

    public static int prim(int[][] graph) {
        int size = graph.length;
        int[] distance = new int[size];
        boolean[] visited = new boolean[size];
        for (int i = 0; i < size; i++) {
            distance[i] = graph[0][i];
        }
        int sum = 0;
        visited[0] = true;
        for (int i = 1; i < size; i++) {
            int minPath = -1;
            int minDistance = Integer.MAX_VALUE;
            for (int j = 0; j < size; j++) {
                if (!visited[j] && distance[i] < minDistance) {
                    minPath = j;
                    minDistance = distance[i];
                }
            }
            if (minPath == -1) {
                return sum;
            }
            sum += minDistance;
            visited[minPath] = true;
            for (int j = 0; j < size; j++) {
                if (!visited[j] && distance[j] > graph[minPath][j]) {
                    distance[j] = graph[minPath][j];
                }
            }
        }
        return sum;
    }

    public static HashMap<Node, Integer> dijkstra1(Node from) {
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(from, 0);
        HashSet<Node> selectedSets = new HashSet<>();
        Node minNode = getMinAndUnseleceedNode(distanceMap, selectedSets);
        while (minNode != null) {
            int distance = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!selectedSets.contains(toNode)) {
                    distanceMap.put(toNode, distance + edge.weight);
                } else {
                    distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            selectedSets.add(minNode);
            minNode = getMinAndUnseleceedNode(distanceMap, selectedSets);
        }
        return distanceMap;
    }

    public static Node getMinAndUnseleceedNode(HashMap<Node, Integer> map, HashSet<Node> selectedSet) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : map.entrySet()) {
            if (!selectedSet.contains(entry.getKey()) && entry.getValue() < minDistance) {
                minNode = entry.getKey();
                minDistance = entry.getValue();
            }
        }
        return minNode;
    }

    public static class NodeRecord {
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    public static class NodeHeap {
        private Node[] nodes; // 实际的堆结构

        private HashMap<Node, Integer> heapIndexMap;
        private HashMap<Node, Integer> distanceMap;
        private int size;

        public NodeHeap(int size) {
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            this.size = size;
        }
        public void addOrUpdatedOrIgnore(Node node, int distance){
            // 在堆裏面,并且沒有被固定過
            if(inHeap(node)){
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                insertHeapify(node, heapIndexMap.get(node));
            }
            // 不在堆裏面
            if(!isEntered(node)){
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(node, size++);
            }
            // 在堆裏面，并且被固定了，此時什麽操作都不做
            // ignore
        }
        public NodeRecord pop(){
            NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            swap(0, size - 1);
            heapIndexMap.put(nodes[size-1], -1);
            distanceMap.remove(nodes[size-1]);
            nodes[size-1] = null;
            heapify(0,--size);
            return nodeRecord;
        }
        private void insertHeapify(Node node, int index) {
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        public void heapify(int index, int size) {
            int left = index * 2 + 1;
            while (left < size) {
                int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left]) ?
                        left + 1 : left;
                smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
                if (smallest == index) {
                    break;
                }
                swap(smallest, index);
                index = smallest;
                left = index * 2 + 1;
            }
        }

        private boolean isEntered(Node node) {
            return heapIndexMap.containsKey(node);
        }

        private boolean inHeap(Node node) {
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }

        public boolean isEmpty() {
            return this.size == 0;
        }

        private void swap(int index1, int index2) {
            heapIndexMap.put(nodes[index1], index2);
            heapIndexMap.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }

        public static HashMap<Node, Integer> dijkstra2(Node head, int size){
            NodeHeap nodeHeap = new NodeHeap(size);
            nodeHeap.addOrUpdatedOrIgnore(head, 0);
            HashMap<Node, Integer> result = new HashMap<>();
            while(!nodeHeap.isEmpty()){
                NodeRecord record = nodeHeap.pop();
                Node cur = record.node;
                int distance = record.distance;
                for(Edge edge: cur.edges){
                    nodeHeap.addOrUpdatedOrIgnore(edge.to, edge.weight+distance);
                }
                result.put(cur,distance);
            }
            return result;
        }

    }
}
